The present invention addresses the problem of provisioning a virtual private network among a set of sites. Pipe and hose models have been utilized by the VPN service providers in order to meet the bandwidth requirements of VPN customers. Although the hose model allows greater flexibility and statistical multiplexing advantages by permitting traffic among hose end points to be distributed arbitrarily, it comes up with provisioning challenges with respect to efficient bandwidth utilization for the VPN service provider.